def partition(seq):
     pi = seq[0]
     lo = [x for x in seq[1:] if x <= pi]
     hi = [x for x in seq[1:] if x > pi]
     return lo, pi, hi

def select(seq, k):
     '''在序列中查找第K小的数'''
     lo, pi, hi = partition(seq)
     m = len(lo)
     if m == k:
          return pi
     elif m < k:
          return select(hi, k - m)
     else:
          return select(lo, k)

if __name__ == '__main__':
     seq = [3, 4, 1, 1, 6, 3, 2, 3, 3, 2, 0, -1]
     print(select(seq, 3))
     print(select(seq, 1))

     seq = [1, 1, 1, 1]
     print(select(seq, 3))
     print(select(seq, 1))
